home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / oasis / ossxmpls.lha / examples / Tsp.d < prev    next >
Encoding:
Text File  |  1992-04-04  |  6.4 KB  |  125 lines
  1. /*======================================================================================================
  2.         Auxiliary  Data  Structures:  task and map
  3. ======================================================================================================*/
  4. class task {                                            # task structure
  5.     attribute:
  6.     public      int*       c1, c2;                      # all cities
  7.                 int*       tour;                        # partial tour
  8.                 int        sum;                         # partial sum
  9. }
  10.  
  11. class map {
  12.     attribute:
  13.     public      int        size;                        # matrix size
  14.                 int[_,_]   dist;                        # distance matrix
  15.     private     int        x = 197;                     # random number seed
  16.     method:
  17.     public      gen        (int I; int* ?Cities).
  18.     private     loop       (int I, J).
  19. }
  20.  
  21. map {
  22.     gen(size, []).
  23.     gen(I', [I|Cs]) |- loop(I,I+1); gen(I+1, Cs').      # go thru rows
  24.  
  25.     loop(_, size).
  26.     loop(I', J') |- x' = (4757 * x + 1) % 32768;
  27.                     (int) B' = 1 + ((x / 16) % 256);    # random number
  28.                     dist[I,J]' = B;                     # initialize (i,j)
  29.                     dist[J,I]' = B;                     # symmetric (j,i)
  30.                     loop(I, J+1).                       # go thru columns
  31. }
  32.  
  33. /*======================================================================================================
  34.         Tsp  Specifications
  35. ======================================================================================================*/
  36. class Tsp {                                             # common Tsp specification
  37.     constant:   int        bignum = 65535;              # greater than all distances
  38.     attribute:
  39.     protected   task*      queue  = [];                 # task queue
  40.     public      int[_,_]   dist   = nil;                # distance matrix
  41.     protected   int*       best   = [];                 # best tour so far
  42.                 int        min    = bignum;             # minimum distance so far
  43.     method:
  44.     protected   explore    (int* C1, C2, Tour; int Sum, Depth).
  45.     private     expand     (int* C1, C2, Tour; int Sum, Depth).
  46.     public      update     (int* Tour; int Sum).
  47.     private     append     (task* In1, In2, ?Out).
  48. }
  49.  
  50. Tsp :: Slave {                                          # Slave specification
  51.     attribute:
  52.     public      Master     master;                      # master agent
  53.     method:
  54.     private     work0      ().                          # mutually recursive
  55.                 work1      ().                          # working routines
  56. }
  57.  
  58. Tsp :: Master[$done] {                                  # Master specification
  59.     method:
  60.     public      run        (int[_,_] Dist; int Depth, Count;
  61.                             int* ?Best; int ?Min).
  62.     private     spawn      (int  Count).
  63.     public      get        (task ?Task; int* ?Best; int ?Min).
  64. }
  65.  
  66. /*======================================================================================================
  67.         Tsp  Implementations
  68. ======================================================================================================*/
  69. Tsp {                                                   # common Tsp code
  70.     explore(_,_,_,S',_) :- min <= S.                    # bounded cutoff, pruned
  71.     explore([],[],T':[X'|_],S',_) |-                    # best tour so far
  72.             update(T,S+dist[X,0]).                      # wrap around for cycle
  73.     explore(C1',C2',T',S',0) |-                         # depth = 0
  74.             append(queue,[task{C1,C2,T,S}],queue').     # enqueue new task
  75.     explore(C1',C2',T',S',D') |-                        # depth > 0
  76.             expand(C1,C2,T,S,D);                        # expand cities
  77.             expand(C2,C1,T,S,D).                        # expand cities
  78.  
  79.     expand([],_,_,_,_).                                 # no more cities
  80.     expand([X'|C1'],C2',T':[Y'|Z'],S',D') |-            # expand partial tour
  81.             explore(C1,C2,[X,Y|Z],S+dist[X,Y],D-1);     # go down 1 level
  82.             expand(C1,[X|C2],T,S,D).                    # expand current level
  83.  
  84.     update(_,S') :- min <= S.                           # new result worst than min?
  85.     update(best',min').                                 # no, update globals
  86.  
  87.     append([],Ys',Ys).
  88.     append([X'|Xs'],Ys',[X|Zs]) |- append(Xs,Ys,Zs').   # append two lists
  89. }
  90.  
  91. Slave {                                                 # Slave code
  92.     ?- work0().                                         # starts a working life...
  93.  
  94.     work1() :- master ! update(best, min), work0().     # update master with result
  95.     work0() :- master ! get(Task',B',M');               # get task from master
  96.                (task) task{C1',C2',T',S'} = Task;       # extract task attributes
  97.                Tsp::update(B,M);                        # update best tour locally
  98.                Tsp::explore(C1,C2,T,S,-1); work1().     # explore search space
  99.     work0().                                            # ...life ends here
  100. }
  101.  
  102. Master {                                                # Master code
  103.     run(dist':$[N',N],Depth',Count',best,min) :-        # user invocation
  104.             best' = [];                                 # no best tour yet
  105.             min'  = bignum;                             # a big number
  106.             (map) Map' = map{N,dist};                   # create map object
  107.             Map ! gen(0,[C'|Cs']);                      # generate random weights
  108.             Tsp::explore(Cs,[],[C],0,Depth);            # generate tasks
  109.             spawn(Count);                               # spawn slave agents
  110.             $done ! wait(Count).                        # wait till all finished
  111.  
  112.     spawn(0).                                           # end of procreation
  113.     spawn(I') |- (Slave) _ = Slave{dist,self};          # spawn a new slave
  114.                  spawn(I-1).                            # spawning more slaves
  115.  
  116.     get(_,best,min) :- queue == []; $done ! post(1).    # queue empty? wakeup!
  117.     get(X,best,min) :- (task*) [X'|queue'] = queue;     # dequeue task
  118.                        X.sum < min.                     # task looks ok?
  119.     get(X,best,min) |- get(X',_,_).                     # no, skip to next task
  120. }
  121.  
  122. /*======================================================================================================
  123.         The  End
  124. ======================================================================================================*/
  125.